class Solution
{
public:
    bool canPartition(vector<int> &nums)
    {
        int s = reduce(nums.begin(), nums.end());
        if (s % 2)
        {
            return false;
        }
        s /= 2;
        int n = nums.size();
        vector<int> f(s + 1);
        f[0] = true;
        for (int i = 0; i < n; i++)
        {
            int x = nums[i];
            for (int j = s; j >= x; j--)
            {
                f[j] = j >= x && f[j - x] || f[j];
                if (f[s])
                {
                    return true;
                }
            }
        }
        return f[s];
    }
};